package com.shr.code_interview;

import java.util.Stack;


/**
 * 用一个栈模拟原始栈，遍历push数组，每次先push，当push元素不等于pop的元素，继续push，直到等于pop的元素；
 * 当等于pop数组的元素，stack弹出，pop元素向后遍历，比较当前栈顶元素，直到
 * 1.stack为空 或 2.pop数组走到最后，3.或pop数组当前元素不等于stack当前的元素
 * 最后如果pop数组走到最后而且模拟栈stack为空，说明是弹出序列，否则不是
 * 
 * @author sevn
 *
 */
public class Solution_31 {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
    	Stack<Integer> stack = new Stack<>();
    	int popIdx = 0 ;
    	for(int i = 0;i < pushA.length; i++){
    		stack.push(pushA[i]) ;
    		if(popA[popIdx] != stack.peek())
    			continue ;
    		else{
    			while(!stack.isEmpty() && popIdx < popA.length && popA[popIdx] == stack.peek()){
    				stack.pop();
    				popIdx++ ;
    			}
    		}
    	}
    	if(popIdx == popA.length && stack.isEmpty())
    		return true ;
    	else return false ;
    }
}
